package com.dyz.leetcode._20_dynamicProgramming;

import java.util.Arrays;
import java.util.List;

public class _322_coinChange {
    public int coinChange(int[] coins, int amount) {
        return dfs(amount, coins);
    }

    private int dfs(int target, int[] coins){

        if(target==0){
            return 0;
        }
        int minCount = Integer.MAX_VALUE;
        for(int i=0; i<coins.length; i++){
            if(target-coins[i]<0){continue;}

            int minSub = dfs(target - coins[i], coins);
            if (minSub==-1){continue;}
            minCount = Math.min(minCount, minSub+1);
        }
        return minCount==Integer.MAX_VALUE?-1:minCount;
    }

    //添加memo去除重复
    public int coinChange1(int[] coins, int amount) {
        int[] memo = new int[amount+1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        return dfs(amount, coins, memo);
    }

    private int dfs(int target, int[] coins, int[] memo){

        if(target==0){
            return 0;
        }
        if(memo[target]!=Integer.MAX_VALUE){
            return memo[target];
        }
        int minCount = Integer.MAX_VALUE;
        for(int i=0; i<coins.length; i++){
            if(target-coins[i]<0){continue;}

            int minSub = dfs(target - coins[i], coins, memo);
            if (minSub==-1){continue;}
            minCount = Math.min(minCount, minSub+1);
        }
        memo[target] = minCount==Integer.MAX_VALUE?-1:minCount;
        return  memo[target];
    }
    public int coinChange2(int[] coins, int amount) {
        int [] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int target = 1; target <= amount; target++) {
            for (int coin:coins) {
                if(target>=coin && dp[target-coin]!=Integer.MAX_VALUE){
                    dp[target] = Math.min(dp[target], dp[target-coin]+1);
                }
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }

    public static void main(String[] args) {
        int[] nums = {1,2,5};
        int amount = 1;
        new _322_coinChange().coinChange2(nums, amount);
    }
}

